//
//  main.c
//  单链表的 OJ 题
//
//  Created by 仲7 on 2024/11/18.
//
#include"List.h"
//链表的 OJ 算法题
//1——删除链表的等于 val 的结点

struct ListNode* removeElements(struct ListNode* head, int val) {
      //方法一：创建新链表，将等于 val 的结点一一尾插到新链表中，最后返回新头结点
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    ListNode* pcur = head;
    //定义 pcur 遍历原链表
    while (pcur)
    {
        //不等于 val 时，尾插新链表
        if (pcur->val != val)
        {
            //分为两种情况：头结点插入和其余
            if (newhead == NULL)
            {
                //头结点时，直接将新结点头尾都指向它
                newhead = newtail = pcur;
            }
            else
            {
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    //如果原链表全是 val或者为空，那么新链表将为空，此时不能对空链表解引用
    if(newhead != NULL){
        newtail->next = NULL;
    }
    return newhead;
}
//-2——反转链表
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL)
    {
        return head;
    }
    ListNode* n1,* n2,* n3;
    n1 = NULL;n2 = head;n3 = n2->next;
    while(n2)
    {
        n2->next = n1;//n2指向改变
        n1 = n2;//n1 后移
        n2 = n3;//n2 后移
        if(n3)//防止结尾n3 走到空，再对空节点解引用
        {
            n3 = n3->next;//n3 后移
        }
    }
    //返回新的头结点
    return n1;
}
//3——找到并返回链表中间节点
struct ListNode* middleNode(struct ListNode* head) {
    //创建快慢指针
    ListNode* slow = head,* fast = head;
    //设置循环条件，遍历链表
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//4——合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //在最初时，处理 list1,2 任意一方为空，或者全空的情况
    if(list1 == NULL)//list1为空，直接把list2传回，当两者均为空时，传回的依旧为空。
    {
        return list2;
    }
    if(list2 == NULL)//同理
    {
        return list1;
    }
    //定义新链表
    ListNode* newhead = NULL,* newtail = NULL;
    //定义两个指针
    ListNode* l1 = list1,* l2 = list2;
    while(l1 && l2)
    {
        if(l1->val <= l2->val)
        {
            //l1 尾插到新链表
            if(newhead == NULL)//当首次尾插时，新链表头结点为空
            {
                newhead = newtail = l1;
                l1 = l1->next;
            }
            else//非头结点插入时
            {
                newtail->next = l1;
                newtail = newtail->next;
                l1 = l1->next;
            }
        }
        else
        {
            //l2 尾插到新链表
            if(newhead == NULL)//当首次尾插时，新链表头结点为空
            {
                newhead = newtail = l2;
                l2 = l2->next;
            }
            else//非头结点插入时
            {
                newtail->next = l2;
                newtail = newtail->next;
                l2 = l2->next;
            }
        }
    }
    //正常运行遍历后，l1 与 l2 只要任意一方为真，另一方就为空
    //直接将不为空的链表继续尾插即可。但是其无法处理最初时链表为空的情况，因为无法对 newtail 空链表解引用。
    if(l1)
    newtail->next = l1;
    if(l2)
    newtail->next = l2;
    return newhead;
}
//4——2 改善上述代码冗余现象
//为 newhead 和 newtail 申请动态空间，让其成为临时节点，以供尾插，去掉头节点单独处理的情况。
struct ListNode* mergeTwoLists2(struct ListNode* list1, struct ListNode* list2) {
    //在最初时，处理 list1,2 任意一方为空，或者全空的情况
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    //定义新链表
    ListNode* newhead,* newtail;
    //为其申请动态空间，让其成为一个临时节点，以供后续插入
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
    //定义两个指针
    ListNode* l1 = list1,* l2 = list2;
    while(l1 && l2)
    {
        if(l1->val <= l2->val)
        {
                newtail->next = l1;
                newtail = newtail->next;
                l1 = l1->next;
        }
        else
        {
                newtail->next = l2;
                newtail = newtail->next;
                l2 = l2->next;
        }
    }
    //正常运行遍历后，l1 与 l2 只要任意一方为真，另一方就为空
    //直接将不为空的链表继续尾插即可。但是其无法处理最初时链表为空的情况，因为无法对 newtail 空链表解引用。
    if(l1)
    newtail->next = l1;
    if(l2)
    newtail->next = l2;
    //末尾要记得释放空间并置空
    //释放之前要先存起来，因为返回值要用
    ListNode* ret = newhead->next;
    free(newhead);
    newhead = NULL;
    //最后返回临时节点的下一个指针，即新的头指针
    return ret;
}
void Test01(void)
{
    //手动输入一个链表
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode*));
    node1->val = 1;
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode*));
    node2->val = 2;
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode*));
    node3->val = 6;
    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode*));
    node4->val = 3;
    ListNode* node5 = (ListNode*)malloc(sizeof(ListNode*));
    node5->val = 6;
    ListNode* plist = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = NULL;
    removeElements(plist, 6);
    SLPrint(plist);
}
int main(int argc, const char * argv[]) {
    Test01();
    return 0;
}
